#include <iostream>
using namespace std;

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class solution
{
    ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        // 判断head为空
        if (!head)
            return nullptr;
        // head 不为空, 但如果m == n, 不逆转
        if (m == n)
            return head;
        ListNode* primary = new ListNode(0), *reverse = new ListNode(0), *tail = primary;
        int count = 1;
        ListNode* cur = head;
        while (cur != nullptr)
        {
            if (count >= m && count <= n)
            {
                // 将区间逆转
                ListNode* next = cur->next;
                cur->next = reverse->next;
                reverse->next = cur;
                cur = next;
            }
            else
            {
                // 将其他元素放到primary
                tail->next = cur;
                cur = cur->next;
                tail = tail->next;
                tail->next = nullptr;
            }
            ++count;
        }
        count = 0;
        cur = primary;
        while (count < m - 1)
        {
            cur = cur->next;
            ++count;
        }
        tail = reverse;
        while (tail->next != nullptr)
        {
            tail = tail->next;
        }
        tail->next = cur->next;
        cur->next = reverse->next;
        head = primary->next;
        return head;
    }
};
